Lagrangian Approaches for a class of Matching Problems in Computational Biology
Identifieur interne : 001196 ( Main/Exploration ); précédent : 001195; suivant : 001197Lagrangian Approaches for a class of Matching Problems in Computational Biology
Auteurs : Nicola Yanev [France] ; Rumen Andonov [France] ; Philippe Veber [France] ; Stefan Balev [France]Source :
Descripteurs français
- mix :
Abstract
Cet article propose des algorithmes efficaces pour déterminer l'alignement optimal entre une structure et une séquence protéique, problème connu sous le nom de protein threading. Nous posons ce problème comme un cas particulier d'appariement. Nous présentons un modèle formel du problème sous la forme d'une famille de graphes, et des programmes en nombre entiers correspondants. Nous étudions dans un premier temps les propriétés de ces modèles, pour ensuite proposer deux approches de relaxation lagrangienne pour la résolution. Enfin, nous montrons, à l'aide de données expérimentales sur des instances réelles, l'efficacité de ces approches. \\ This paper presents efficient algorithms for solving the problem of aligning a protein structure template to a query amino-acid sequence, known as protein threading problem. We consider the problem as a special case of graph matching problem. We give formal graph and integer programming models of the problem. After studying the properties of these models, we propose two kinds of Lagrangian relaxation for solving them. We present experimental results on real life instances showing the efficiency of our approaches.
Url:
Affiliations:
- France
- Haute-Normandie, Région Bretagne, Région Normandie
- Le Havre, Rennes
- Université de Rennes 1, Université du Havre, Université européenne de Bretagne
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 000198
- to stream Hal, to step Curation: 000198
- to stream Hal, to step Checkpoint: 000709
- to stream Main, to step Merge: 001221
- to stream Main, to step Curation: 001196
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Lagrangian Approaches for a class of Matching Problems in Computational Biology</title><author><name sortKey="Yanev, Nicola" sort="Yanev, Nicola" uniqKey="Yanev N" first="Nicola" last="Yanev">Nicola Yanev</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2535" status="OLD"> <idno type="RNSR">200218338D</idno> <orgName>Biological systems and models, bioinformatics and sequences</orgName> <orgName type="acronym">SYMBIOSE</orgName> <date type="start">2002-03-15</date> <date type="end">2011-12-31</date> <desc> <address> <addrLine>Campus de Beaulieu, 35042 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/equipes/symbiose</ref> </desc> <listRelation> <relation active="#struct-2494" type="direct"></relation> <relation active="#struct-105160" type="indirect"></relation> <relation active="#struct-117606" type="indirect"></relation> <relation active="#struct-300009" type="indirect"></relation> <relation name="UMR6074" active="#struct-441569" type="indirect"></relation> <relation active="#struct-419153" type="direct"></relation> </listRelation><tutelles><tutelle active="#struct-2494" type="direct"><org type="laboratory" xml:id="struct-2494" status="OLD"> <orgName>Institut de Recherche en Informatique et Systèmes Aléatoires</orgName> <orgName type="acronym">IRISA</orgName> <desc> <address> <addrLine>Campus universitaire de Beaulieu - 35042 Rennes</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.irisa.fr/</ref> </desc> <listRelation> <relation active="#struct-105160" type="direct"></relation> <relation active="#struct-117606" type="direct"></relation> <relation active="#struct-300009" type="direct"></relation> <relation name="UMR6074" active="#struct-441569" type="direct"></relation> </listRelation></org></tutelle><tutelle active="#struct-105160" type="indirect"><org type="institution" xml:id="struct-105160" status="VALID"> <orgName>Université de Rennes 1</orgName> <orgName type="acronym">UR1</orgName> <desc> <address> <addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.univ-rennes1.fr/</ref> </desc></org></tutelle><tutelle active="#struct-117606" type="indirect"><org type="institution" xml:id="struct-117606" status="VALID"> <orgName>Institut National des Sciences Appliquées - Rennes</orgName> <orgName type="acronym">INSA Rennes</orgName> <desc> <address> <addrLine>20, avenue des Buttes de Coësmes - CS 70839 - 35708 Rennes cedex 7</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.insa-rennes.fr/</ref> </desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle name="UMR6074" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-419153" type="direct"><org type="laboratory" xml:id="struct-419153" status="VALID"> <idno type="RNSR">198018249C</idno> <orgName>Inria Rennes – Bretagne Atlantique </orgName> <desc> <address> <addrLine>Campus de beaulieu35042 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/centre/rennes</ref> </desc> <listRelation> <relation active="#struct-300009" type="direct"></relation> </listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Rennes</settlement><region type="region" nuts="2">Région Bretagne</region></placeName><orgName type="university">Université de Rennes 1</orgName><orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName></affiliation></author><author><name sortKey="Andonov, Rumen" sort="Andonov, Rumen" uniqKey="Andonov R" first="Rumen" last="Andonov">Rumen Andonov</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2535" status="OLD"> <idno type="RNSR">200218338D</idno> <orgName>Biological systems and models, bioinformatics and sequences</orgName> <orgName type="acronym">SYMBIOSE</orgName> <date type="start">2002-03-15</date> <date type="end">2011-12-31</date> <desc> <address> <addrLine>Campus de Beaulieu, 35042 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/equipes/symbiose</ref> </desc> <listRelation> <relation active="#struct-2494" type="direct"></relation> <relation active="#struct-105160" type="indirect"></relation> <relation active="#struct-117606" type="indirect"></relation> <relation active="#struct-300009" type="indirect"></relation> <relation name="UMR6074" active="#struct-441569" type="indirect"></relation> <relation active="#struct-419153" type="direct"></relation> </listRelation><tutelles><tutelle active="#struct-2494" type="direct"><org type="laboratory" xml:id="struct-2494" status="OLD"> <orgName>Institut de Recherche en Informatique et Systèmes Aléatoires</orgName> <orgName type="acronym">IRISA</orgName> <desc> <address> <addrLine>Campus universitaire de Beaulieu - 35042 Rennes</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.irisa.fr/</ref> </desc> <listRelation> <relation active="#struct-105160" type="direct"></relation> <relation active="#struct-117606" type="direct"></relation> <relation active="#struct-300009" type="direct"></relation> <relation name="UMR6074" active="#struct-441569" type="direct"></relation> </listRelation></org></tutelle><tutelle active="#struct-105160" type="indirect"><org type="institution" xml:id="struct-105160" status="VALID"> <orgName>Université de Rennes 1</orgName> <orgName type="acronym">UR1</orgName> <desc> <address> <addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.univ-rennes1.fr/</ref> </desc></org></tutelle><tutelle active="#struct-117606" type="indirect"><org type="institution" xml:id="struct-117606" status="VALID"> <orgName>Institut National des Sciences Appliquées - Rennes</orgName> <orgName type="acronym">INSA Rennes</orgName> <desc> <address> <addrLine>20, avenue des Buttes de Coësmes - CS 70839 - 35708 Rennes cedex 7</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.insa-rennes.fr/</ref> </desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle name="UMR6074" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-419153" type="direct"><org type="laboratory" xml:id="struct-419153" status="VALID"> <idno type="RNSR">198018249C</idno> <orgName>Inria Rennes – Bretagne Atlantique </orgName> <desc> <address> <addrLine>Campus de beaulieu35042 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/centre/rennes</ref> </desc> <listRelation> <relation active="#struct-300009" type="direct"></relation> </listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Rennes</settlement><region type="region" nuts="2">Région Bretagne</region></placeName><orgName type="university">Université de Rennes 1</orgName><orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName></affiliation></author><author><name sortKey="Veber, Philippe" sort="Veber, Philippe" uniqKey="Veber P" first="Philippe" last="Veber">Philippe Veber</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2535" status="OLD"> <idno type="RNSR">200218338D</idno> <orgName>Biological systems and models, bioinformatics and sequences</orgName> <orgName type="acronym">SYMBIOSE</orgName> <date type="start">2002-03-15</date> <date type="end">2011-12-31</date> <desc> <address> <addrLine>Campus de Beaulieu, 35042 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/equipes/symbiose</ref> </desc> <listRelation> <relation active="#struct-2494" type="direct"></relation> <relation active="#struct-105160" type="indirect"></relation> <relation active="#struct-117606" type="indirect"></relation> <relation active="#struct-300009" type="indirect"></relation> <relation name="UMR6074" active="#struct-441569" type="indirect"></relation> <relation active="#struct-419153" type="direct"></relation> </listRelation><tutelles><tutelle active="#struct-2494" type="direct"><org type="laboratory" xml:id="struct-2494" status="OLD"> <orgName>Institut de Recherche en Informatique et Systèmes Aléatoires</orgName> <orgName type="acronym">IRISA</orgName> <desc> <address> <addrLine>Campus universitaire de Beaulieu - 35042 Rennes</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.irisa.fr/</ref> </desc> <listRelation> <relation active="#struct-105160" type="direct"></relation> <relation active="#struct-117606" type="direct"></relation> <relation active="#struct-300009" type="direct"></relation> <relation name="UMR6074" active="#struct-441569" type="direct"></relation> </listRelation></org></tutelle><tutelle active="#struct-105160" type="indirect"><org type="institution" xml:id="struct-105160" status="VALID"> <orgName>Université de Rennes 1</orgName> <orgName type="acronym">UR1</orgName> <desc> <address> <addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.univ-rennes1.fr/</ref> </desc></org></tutelle><tutelle active="#struct-117606" type="indirect"><org type="institution" xml:id="struct-117606" status="VALID"> <orgName>Institut National des Sciences Appliquées - Rennes</orgName> <orgName type="acronym">INSA Rennes</orgName> <desc> <address> <addrLine>20, avenue des Buttes de Coësmes - CS 70839 - 35708 Rennes cedex 7</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.insa-rennes.fr/</ref> </desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle name="UMR6074" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-419153" type="direct"><org type="laboratory" xml:id="struct-419153" status="VALID"> <idno type="RNSR">198018249C</idno> <orgName>Inria Rennes – Bretagne Atlantique </orgName> <desc> <address> <addrLine>Campus de beaulieu35042 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/centre/rennes</ref> </desc> <listRelation> <relation active="#struct-300009" type="direct"></relation> </listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Rennes</settlement><region type="region" nuts="2">Région Bretagne</region></placeName><orgName type="university">Université de Rennes 1</orgName><orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName></affiliation></author><author><name sortKey="Balev, Stefan" sort="Balev, Stefan" uniqKey="Balev S" first="Stefan" last="Balev">Stefan Balev</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-16687" status="VALID"> <orgName>Laboratoire d'informatique du Havre</orgName> <orgName type="acronym">LIH EA3219</orgName> <desc> <address> <addrLine>25 rue Philippe Lebon, BP 540 76058 Le Havre cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www-lih.univ-lehavre.fr/presentation.html</ref> </desc> <listRelation> <relation active="#struct-300317" type="direct"></relation> </listRelation><tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Le Havre</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université du Havre</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00091944</idno><idno type="halId">inria-00091944</idno><idno type="halUri">https://hal.inria.fr/inria-00091944</idno><idno type="url">https://hal.inria.fr/inria-00091944</idno><date when="2006">2006</date><idno type="wicri:Area/Hal/Corpus">000198</idno><idno type="wicri:Area/Hal/Curation">000198</idno><idno type="wicri:Area/Hal/Checkpoint">000709</idno><idno type="wicri:Area/Main/Merge">001221</idno><idno type="wicri:Area/Main/Curation">001196</idno><idno type="wicri:Area/Main/Exploration">001196</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Lagrangian Approaches for a class of Matching Problems in Computational Biology</title><author><name sortKey="Yanev, Nicola" sort="Yanev, Nicola" uniqKey="Yanev N" first="Nicola" last="Yanev">Nicola Yanev</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2535" status="OLD"> <idno type="RNSR">200218338D</idno> <orgName>Biological systems and models, bioinformatics and sequences</orgName> <orgName type="acronym">SYMBIOSE</orgName> <date type="start">2002-03-15</date> <date type="end">2011-12-31</date> <desc> <address> <addrLine>Campus de Beaulieu, 35042 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/equipes/symbiose</ref> </desc> <listRelation> <relation active="#struct-2494" type="direct"></relation> <relation active="#struct-105160" type="indirect"></relation> <relation active="#struct-117606" type="indirect"></relation> <relation active="#struct-300009" type="indirect"></relation> <relation name="UMR6074" active="#struct-441569" type="indirect"></relation> <relation active="#struct-419153" type="direct"></relation> </listRelation><tutelles><tutelle active="#struct-2494" type="direct"><org type="laboratory" xml:id="struct-2494" status="OLD"> <orgName>Institut de Recherche en Informatique et Systèmes Aléatoires</orgName> <orgName type="acronym">IRISA</orgName> <desc> <address> <addrLine>Campus universitaire de Beaulieu - 35042 Rennes</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.irisa.fr/</ref> </desc> <listRelation> <relation active="#struct-105160" type="direct"></relation> <relation active="#struct-117606" type="direct"></relation> <relation active="#struct-300009" type="direct"></relation> <relation name="UMR6074" active="#struct-441569" type="direct"></relation> </listRelation></org></tutelle><tutelle active="#struct-105160" type="indirect"><org type="institution" xml:id="struct-105160" status="VALID"> <orgName>Université de Rennes 1</orgName> <orgName type="acronym">UR1</orgName> <desc> <address> <addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.univ-rennes1.fr/</ref> </desc></org></tutelle><tutelle active="#struct-117606" type="indirect"><org type="institution" xml:id="struct-117606" status="VALID"> <orgName>Institut National des Sciences Appliquées - Rennes</orgName> <orgName type="acronym">INSA Rennes</orgName> <desc> <address> <addrLine>20, avenue des Buttes de Coësmes - CS 70839 - 35708 Rennes cedex 7</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.insa-rennes.fr/</ref> </desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle name="UMR6074" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-419153" type="direct"><org type="laboratory" xml:id="struct-419153" status="VALID"> <idno type="RNSR">198018249C</idno> <orgName>Inria Rennes – Bretagne Atlantique </orgName> <desc> <address> <addrLine>Campus de beaulieu35042 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/centre/rennes</ref> </desc> <listRelation> <relation active="#struct-300009" type="direct"></relation> </listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Rennes</settlement><region type="region" nuts="2">Région Bretagne</region></placeName><orgName type="university">Université de Rennes 1</orgName><orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName></affiliation></author><author><name sortKey="Andonov, Rumen" sort="Andonov, Rumen" uniqKey="Andonov R" first="Rumen" last="Andonov">Rumen Andonov</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2535" status="OLD"> <idno type="RNSR">200218338D</idno> <orgName>Biological systems and models, bioinformatics and sequences</orgName> <orgName type="acronym">SYMBIOSE</orgName> <date type="start">2002-03-15</date> <date type="end">2011-12-31</date> <desc> <address> <addrLine>Campus de Beaulieu, 35042 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/equipes/symbiose</ref> </desc> <listRelation> <relation active="#struct-2494" type="direct"></relation> <relation active="#struct-105160" type="indirect"></relation> <relation active="#struct-117606" type="indirect"></relation> <relation active="#struct-300009" type="indirect"></relation> <relation name="UMR6074" active="#struct-441569" type="indirect"></relation> <relation active="#struct-419153" type="direct"></relation> </listRelation><tutelles><tutelle active="#struct-2494" type="direct"><org type="laboratory" xml:id="struct-2494" status="OLD"> <orgName>Institut de Recherche en Informatique et Systèmes Aléatoires</orgName> <orgName type="acronym">IRISA</orgName> <desc> <address> <addrLine>Campus universitaire de Beaulieu - 35042 Rennes</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.irisa.fr/</ref> </desc> <listRelation> <relation active="#struct-105160" type="direct"></relation> <relation active="#struct-117606" type="direct"></relation> <relation active="#struct-300009" type="direct"></relation> <relation name="UMR6074" active="#struct-441569" type="direct"></relation> </listRelation></org></tutelle><tutelle active="#struct-105160" type="indirect"><org type="institution" xml:id="struct-105160" status="VALID"> <orgName>Université de Rennes 1</orgName> <orgName type="acronym">UR1</orgName> <desc> <address> <addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.univ-rennes1.fr/</ref> </desc></org></tutelle><tutelle active="#struct-117606" type="indirect"><org type="institution" xml:id="struct-117606" status="VALID"> <orgName>Institut National des Sciences Appliquées - Rennes</orgName> <orgName type="acronym">INSA Rennes</orgName> <desc> <address> <addrLine>20, avenue des Buttes de Coësmes - CS 70839 - 35708 Rennes cedex 7</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.insa-rennes.fr/</ref> </desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle name="UMR6074" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-419153" type="direct"><org type="laboratory" xml:id="struct-419153" status="VALID"> <idno type="RNSR">198018249C</idno> <orgName>Inria Rennes – Bretagne Atlantique </orgName> <desc> <address> <addrLine>Campus de beaulieu35042 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/centre/rennes</ref> </desc> <listRelation> <relation active="#struct-300009" type="direct"></relation> </listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Rennes</settlement><region type="region" nuts="2">Région Bretagne</region></placeName><orgName type="university">Université de Rennes 1</orgName><orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName></affiliation></author><author><name sortKey="Veber, Philippe" sort="Veber, Philippe" uniqKey="Veber P" first="Philippe" last="Veber">Philippe Veber</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2535" status="OLD"> <idno type="RNSR">200218338D</idno> <orgName>Biological systems and models, bioinformatics and sequences</orgName> <orgName type="acronym">SYMBIOSE</orgName> <date type="start">2002-03-15</date> <date type="end">2011-12-31</date> <desc> <address> <addrLine>Campus de Beaulieu, 35042 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/equipes/symbiose</ref> </desc> <listRelation> <relation active="#struct-2494" type="direct"></relation> <relation active="#struct-105160" type="indirect"></relation> <relation active="#struct-117606" type="indirect"></relation> <relation active="#struct-300009" type="indirect"></relation> <relation name="UMR6074" active="#struct-441569" type="indirect"></relation> <relation active="#struct-419153" type="direct"></relation> </listRelation><tutelles><tutelle active="#struct-2494" type="direct"><org type="laboratory" xml:id="struct-2494" status="OLD"> <orgName>Institut de Recherche en Informatique et Systèmes Aléatoires</orgName> <orgName type="acronym">IRISA</orgName> <desc> <address> <addrLine>Campus universitaire de Beaulieu - 35042 Rennes</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.irisa.fr/</ref> </desc> <listRelation> <relation active="#struct-105160" type="direct"></relation> <relation active="#struct-117606" type="direct"></relation> <relation active="#struct-300009" type="direct"></relation> <relation name="UMR6074" active="#struct-441569" type="direct"></relation> </listRelation></org></tutelle><tutelle active="#struct-105160" type="indirect"><org type="institution" xml:id="struct-105160" status="VALID"> <orgName>Université de Rennes 1</orgName> <orgName type="acronym">UR1</orgName> <desc> <address> <addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.univ-rennes1.fr/</ref> </desc></org></tutelle><tutelle active="#struct-117606" type="indirect"><org type="institution" xml:id="struct-117606" status="VALID"> <orgName>Institut National des Sciences Appliquées - Rennes</orgName> <orgName type="acronym">INSA Rennes</orgName> <desc> <address> <addrLine>20, avenue des Buttes de Coësmes - CS 70839 - 35708 Rennes cedex 7</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.insa-rennes.fr/</ref> </desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle name="UMR6074" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-419153" type="direct"><org type="laboratory" xml:id="struct-419153" status="VALID"> <idno type="RNSR">198018249C</idno> <orgName>Inria Rennes – Bretagne Atlantique </orgName> <desc> <address> <addrLine>Campus de beaulieu35042 Rennes cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/centre/rennes</ref> </desc> <listRelation> <relation active="#struct-300009" type="direct"></relation> </listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Rennes</settlement><region type="region" nuts="2">Région Bretagne</region></placeName><orgName type="university">Université de Rennes 1</orgName><orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName></affiliation></author><author><name sortKey="Balev, Stefan" sort="Balev, Stefan" uniqKey="Balev S" first="Stefan" last="Balev">Stefan Balev</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-16687" status="VALID"> <orgName>Laboratoire d'informatique du Havre</orgName> <orgName type="acronym">LIH EA3219</orgName> <desc> <address> <addrLine>25 rue Philippe Lebon, BP 540 76058 Le Havre cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www-lih.univ-lehavre.fr/presentation.html</ref> </desc> <listRelation> <relation active="#struct-300317" type="direct"></relation> </listRelation><tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Le Havre</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université du Havre</orgName></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="fr"><term>Alignement séquence-structure</term><term>Lagrangian relaxatio</term><term>complexity</term><term>complexité</term><term>integer programming</term><term>programmation en nombres entiers</term><term>relaxation lagrangienne \\ Sequence-structure alignment</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Cet article propose des algorithmes efficaces pour déterminer l'alignement optimal entre une structure et une séquence protéique, problème connu sous le nom de protein threading. Nous posons ce problème comme un cas particulier d'appariement. Nous présentons un modèle formel du problème sous la forme d'une famille de graphes, et des programmes en nombre entiers correspondants. Nous étudions dans un premier temps les propriétés de ces modèles, pour ensuite proposer deux approches de relaxation lagrangienne pour la résolution. Enfin, nous montrons, à l'aide de données expérimentales sur des instances réelles, l'efficacité de ces approches. \\ This paper presents efficient algorithms for solving the problem of aligning a protein structure template to a query amino-acid sequence, known as protein threading problem. We consider the problem as a special case of graph matching problem. We give formal graph and integer programming models of the problem. After studying the properties of these models, we propose two kinds of Lagrangian relaxation for solving them. We present experimental results on real life instances showing the efficiency of our approaches.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Haute-Normandie</li><li>Région Bretagne</li><li>Région Normandie</li></region><settlement><li>Le Havre</li><li>Rennes</li></settlement><orgName><li>Université de Rennes 1</li><li>Université du Havre</li><li>Université européenne de Bretagne</li></orgName></list><tree><country name="France"><region name="Région Bretagne"><name sortKey="Yanev, Nicola" sort="Yanev, Nicola" uniqKey="Yanev N" first="Nicola" last="Yanev">Nicola Yanev</name></region><name sortKey="Andonov, Rumen" sort="Andonov, Rumen" uniqKey="Andonov R" first="Rumen" last="Andonov">Rumen Andonov</name><name sortKey="Balev, Stefan" sort="Balev, Stefan" uniqKey="Balev S" first="Stefan" last="Balev">Stefan Balev</name><name sortKey="Veber, Philippe" sort="Veber, Philippe" uniqKey="Veber P" first="Philippe" last="Veber">Philippe Veber</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/France/explor/LeHavreV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001196 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001196 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/France
|area= LeHavreV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:inria-00091944
|texte= Lagrangian Approaches for a class of Matching Problems in Computational Biology
}}
| This area was generated with Dilib version V0.6.25. |  |